package com.lw.leetcode.bingChaJi.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 并查集示例
 * 看了解题
 * 1697. 检查边长度限制的路径是否存在
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/14 9:34
 */
public class DistanceLimitedPathsExist {

    private int[] arr;

    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
        this.arr = new int[n];
        int length = edgeList.length;
        int len = queries.length;

        int[][] cas = new int[len][4];

        for (int i = 0; i < len; i++) {
            int[] query = queries[i];
            int[] ca = cas[i];
            ca[0] = query[0];
            ca[1] = query[1];
            ca[2] = query[2];
            ca[3] = i;
        }
        Arrays.sort(edgeList, (a, b) -> Integer.compare(a[2], b[2]));
        Arrays.sort(cas, (a, b) -> Integer.compare(a[2], b[2]));
        for (int i = 0; i < n; i++) {
            arr[i] = i;
        }
        boolean[] flags = new boolean[len];
        int index = 0;
        for (int i = 0; i < len; i++) {
            int[] ints = cas[i];
            int c = ints[2];
            while (index < length && edgeList[index][2] < c) {
                int[] items = edgeList[index];
                arr[find(items[1])] = find(items[0]);
                index++;
            }
            flags[ints[3]] = find(ints[0]) == find(ints[1]);
        }
        return flags;
    }

    private int find(int t) {
        if (arr[t] == t) {
            return t;
        }
        arr[t] = find(arr[t]);
        return arr[t];
    }

}
